Compression programs routinely limit the data to be compressed together in segments called windows. The process of doing this is called windowing. Delta compression techniques were developed to compress a target file given some other related source file. An early example delta compressor was the UNIX diff tool which computes differences between versions of text files by matching text lines across files. Diff was used to reduce disk storage in UNIX based source code control systems such as Source Code Control System (SCCS) and Revision Control System (RCS). One of the first delta compressors that could deal with binary data was Vdelta. Unlike other delta compressors which do nothing without source data, the algorithm used in Vdelta compresses data when source data is absent. Vdelta was used in the Bell Labs source and binary code control system (SBCS) and later in the experiments that spurred the addition of delta-encoding to the Internet HTTP protocol. Windowing is necessary to delta compressors partly due to their use of memory-intensive string matching algorithms and partly due to improved coding of addresses of matches. Here, windowing means first dividing a target file into data segments called target windows, then for each target window selecting some suitably similar source window to compress against. Current practice uses source data with matching file offsets to given target windows. This may work for file versions created by simple editing but often fails when significant data updates happen between versions.
Therefore, a need exists for a method for efficiently matching target file windows with source file windows to improve delta compression performance.